
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef char DataType;

//采用链式栈 
struct node{
    DataType data;  //数据元素
    struct node *next; //指向下一个数据元素的指针
};

typedef struct node *PtrToNode;
typedef PtrToNode Stack;

//初始化一个空栈 
Stack createNullStack(void)
{
    PtrToNode head = (struct node* )malloc(sizeof(struct node));
    head->next = NULL;
    return head;
}

//入栈函数，参数：入栈数据元素，栈头指针
void push(DataType x , Stack s)
{
    //请在此处填写代码，实现入栈操作
    /********** Begin **********/
    Stack l=(Stack)malloc(sizeof(struct node));
    l->data=x;
    l->next=s->next;
    s->next=l;
    /********** End **********/
}

//判定栈是否为空，若栈为空，则返回1，否则返回0 
int isEmpty(Stack s)
{
    //请在此处填写代码，实现判定栈是否为空操作，若栈为空，则返回1，否则返回0
    /********** Begin **********/
    return s->next==NULL;

    /********** End **********/
}

//出栈，并返回栈顶元素
DataType pop(Stack s)
{
    if(isEmpty(s) == 0)
    {
        DataType x = s->next->data;
        PtrToNode p = s->next ;
        s->next = p->next ;
        free(p) ;
        return x ;
    }
    else
        return 0;
}

void balance( char str[])
{
    //请在此处填写代码，实现平衡符号的判定,若判断不匹配， 输出  不匹配， 否则输出  匹配
    /********** Begin **********/
    Stack l=createNullStack();
    for (int i = 0; str[i]!='\0'; ++i)
    {
        switch (str[i])
        {
            case'[': push(']',l);
            break;
            case '{':push('}',l);
                break;
            case'(':push(')',l);
                break;
            case'}':
            case ')':
            case ']':
                if (str[i]!=pop(l))
                {
                    printf("不匹配");
                    return;
                }
                break;
        }
    }
    if (isEmpty(l))
    printf("匹配");
    else
        printf("不匹配");
    /********** End **********/
}

int main()
{
    char str[90] ;
    gets(str) ;
    balance(str);
}
 